﻿//Author: Paweł Kaftan
//Comments and names of regions refer to: http://arxiv.org/pdf/1405.6347.pdf
using System;
using System.Collections.Generic;
using System.Linq;
using System.Diagnostics;

namespace HamiltonianCycle
{
    partial class Program
    {
        static List<int>[] graph, oppositeGraph;
        static List<int> HamiltonianCycle, verticesWithSubsets, addedEdges, newVerticesWithSubsets, originalVerticesWithSubsets;
        static bool endOfSearch, endOfAlgorithm, combinationFound;
        static int level, stage, limit;
        static Stopwatch timer;
        static List<int> Algorithm(List<int>[] graphArgument)
        {
            endOfAlgorithm = false;
            HamiltonianCycle = new List<int>();
            for (int time = 2; ; time += 2)
                for (stage = 1; stage <= 5; ++stage) //9.1
                {
                    graph = SaveGraph(graphArgument);
                    RemoveMultipleEdgesAndLoops(graph); //3.1
                    if (stage == 5)
                        graph = GetReversedGraph(graph); //6
                    ClearVariables();
                    limit = graphArgument.Length * graphArgument.Length * time;
                    oppositeGraph = GetOppositeGraph(graph); //2.7
                    endOfAlgorithm = AnalyzeGraph(graph, oppositeGraph, new List<Edge>(), true, true); //8.1.a
                    if (stage != 2)
                        FindHamiltonianCycle(GetNextVertex()); //7.3.1
                    else
                    {
                        List<int>[] testedGraph = SaveGraph(graph);
                        foreach (int a in GetCorrectOrder(graph))
                        {
                            limit /= 2;
                            ClearVariables();
                            RestoreGraphs(testedGraph);
                            FindHamiltonianCycle(a); //7.3.2
                            if (endOfAlgorithm)
                                return HamiltonianCycle;
                        }
                    }
                    if (endOfAlgorithm)
                        return HamiltonianCycle;
                }
        }
        static void FindHamiltonianCycle(int a)
        {
            if (!endOfSearch && !endOfAlgorithm)
            {
                ++level;
                if (HamiltonianCycleFound())
                    endOfAlgorithm = true;
                SortList(a); //7.4
                for (int b = 0; b < graph[a].Count && !endOfSearch && !endOfAlgorithm && timer.ElapsedMilliseconds < limit; ++b)
                {
                    List<Edge> removedEdges = new List<Edge>();
                    int chosenVertex = graph[a][b];
                    List<int>[] currentGraph = SaveGraph(graph);
                    graph[a].Remove(chosenVertex);
                    #region 8.2
                    foreach (int c in graph[a])
                    {
                        removedEdges.Add(new Edge(a, c));
                        oppositeGraph[c].Remove(a);
                    }
                    graph[a].Clear();
                    #endregion
                    graph[a].Add(chosenVertex);
                    bool HamiltonianCycleCantExist = AnalyzeGraph(graph, oppositeGraph, removedEdges, true, false); //8.1.b
                    if (!HamiltonianCycleCantExist)
                    {
                        if (stage != 2)
                            FindHamiltonianCycle(GetNextVertex()); //7.5.1
                        else
                            FindHamiltonianCycle(chosenVertex); //7.5.2
                        RestoreGraphs(currentGraph); //8.4
                    }
                    else
                        foreach (Edge e in removedEdges) //8.3
                        {
                            graph[e.from].Add(e.to);
                            oppositeGraph[e.to].Add(e.from);
                        }
                }
                if (!endOfSearch && !endOfAlgorithm)
                {
                    if (timer.ElapsedMilliseconds >= limit)
                        endOfSearch = true;
                    --level;
                    if (level == 0 && !endOfSearch)
                        endOfAlgorithm = true;
                }
            }
        }
        static bool HamiltonianCycleFound()
        {
            foreach (List<int> list in graph)
                if (list.Count != 1)
                    return false;
            HamiltonianCycle = GetHamiltonianCycle(graph);
            if (stage == 5)
                for (int a = 0; a < HamiltonianCycle.Count; ++a)
                    HamiltonianCycle[a] = graph.Length - HamiltonianCycle[a] - 1;
            return true;
        }
        static void ClearVariables()
        {
            endOfSearch = false;
            level = 0;
            timer = Stopwatch.StartNew();
        }
        static List<int> GetHamiltonianCycle(List<int>[] graphArgument)
        {
            List<int> cycle = new List<int>() { 0 };
            while (true)
            {
                if (cycle.Count == graphArgument.Length && graphArgument[cycle.Last()].Contains(cycle[0]))
                    return cycle;
                if (cycle.Contains(graphArgument[cycle.Last()][0]))
                    return new List<int>();
                else
                    cycle.Add(graphArgument[cycle.Last()][0]);
            }
        }
        static int GetNextVertex() //7.5.1
        {
            List<int> correctOrder = GetCorrectOrder(graph);
            foreach (int a in correctOrder)
                if (graph[a].Count != 1)
                    return a;
            return 0;
        }
        static bool AnalyzeGraph(List<int>[] graphArgument, List<int>[] graphOppositeArgument, List<Edge> removedEdges, bool FECR, bool fullAnalysis)
        {
            bool HamiltonianCycleCantExist = false;
            int b = 0;
            List<int> changedVerticesInGraph, changedVerticesInOppositeGraph;
            do
            {
                changedVerticesInGraph = new List<int>();
                changedVerticesInOppositeGraph = new List<int>();
                for (int c = b; c < removedEdges.Count; ++c)
                {
                    changedVerticesInGraph.Add(removedEdges[c].from);
                    changedVerticesInOppositeGraph.Add(removedEdges[c].to);
                }
                changedVerticesInGraph = changedVerticesInGraph.Distinct().ToList();
                changedVerticesInOppositeGraph = changedVerticesInOppositeGraph.Distinct().ToList();
                if (!fullAnalysis) //9.2.2
                {
                    for (int d = 0; d < changedVerticesInGraph.Count; ++d)
                        FindImporatantVertices(changedVerticesInGraph[d], graphArgument, changedVerticesInGraph);
                    for (int d = 0; d < changedVerticesInOppositeGraph.Count; ++d)
                        FindImporatantVertices(changedVerticesInOppositeGraph[d], graphOppositeArgument, changedVerticesInOppositeGraph);
                }
                b = removedEdges.Count;
                HamiltonianCycleCantExist = RemoveUnnecessaryEdges(graphArgument, graphOppositeArgument, removedEdges, false, changedVerticesInGraph, fullAnalysis, FECR);
                if (!HamiltonianCycleCantExist)
                    HamiltonianCycleCantExist = RemoveUnnecessaryEdges(graphOppositeArgument, graphArgument, removedEdges, true, changedVerticesInOppositeGraph, fullAnalysis, FECR);
            }
            while (b != removedEdges.Count && !HamiltonianCycleCantExist);
            if (!HamiltonianCycleCantExist)
                HamiltonianCycleCantExist = GraphIsDisconnected(graphArgument); //4.3
            return HamiltonianCycleCantExist;
        }
        static bool RemoveUnnecessaryEdges(List<int>[] graphArgument, List<int>[] oppositeGraphArgument, List<Edge> removedEdges, bool oppositeGraph, List<int> changedVertices, bool fullAnalysis, bool FECR)
        {
            bool HamiltonianCycleCantExist = false;
            if (fullAnalysis)
                changedVertices = GetCorrectOrder(graphArgument);
            for (int a = 0; a < changedVertices.Count && timer.ElapsedMilliseconds < limit; ++a)
            {
                int a_ = changedVertices[a];
                if (graphArgument[a_].Count == 1 && graphArgument[graphArgument[a_][0]].Contains(a_)) //3.3
                {
                    if (!oppositeGraph)
                        RemoveEdge(new Edge(graphArgument[a_][0], a_), graphArgument, oppositeGraphArgument, removedEdges);
                    else
                        RemoveEdge(new Edge(a_, graphArgument[a_][0]), oppositeGraphArgument, graphArgument, removedEdges);
                }
                if (UniqueNeighboursTest(a_, graphArgument, oppositeGraphArgument, removedEdges, oppositeGraph, new List<int>())) //3.2.1
                    return true;
                originalVerticesWithSubsets = new List<int>();
                foreach (int b in verticesWithSubsets)
                    originalVerticesWithSubsets.Add(b);
                if (stage >= 3 && stage <= 4)
                {
                    List<List<int>> lists = new List<List<int>>();
                    GetAddedEdges(a_, graphArgument, lists, new List<int>()); //3.2.3
                    List<AddedEdges> ListOfAddedEdges = new List<AddedEdges>();
                    for (int c = 0; c < lists.Count; ++c)
                    {
                        if (UniqueNeighboursTest(a_, graphArgument, oppositeGraphArgument, removedEdges, oppositeGraph, lists[c])) //3.2.2
                            return true;
                        if (stage == 3 && level == 0) //3.2.4
                        {
                            List<int> vertices = new List<int>();
                            foreach (int d in lists[c])
                                vertices.Add(d);
                            List<int> subsets = new List<int>();
                            foreach (int d in verticesWithSubsets)
                                if (!originalVerticesWithSubsets.Contains(d))
                                    subsets.Add(d);
                            if (vertices.Count <= subsets.Count)
                                ListOfAddedEdges.Add(new AddedEdges(vertices, subsets));
                        }
                    }
                    if (stage == 3 && level == 0) //3.2.4
                    {
                        ListOfAddedEdges = ListOfAddedEdges.OrderBy(p => p.edges.Count).Reverse().ToList();
                        combinationFound = false;
                        if (ListOfAddedEdges.Count > 0)
                            for (int d = 0; d < ListOfAddedEdges.Count && !combinationFound; ++d)
                            {
                                addedEdges = new List<int>();
                                newVerticesWithSubsets = new List<int>();
                                SearchForCombinationOfAddedEdges(d, a_, graphArgument, ListOfAddedEdges); //3.2.4
                            }
                        if (combinationFound)
                            if (UniqueNeighboursTest(a_, graphArgument, oppositeGraphArgument, removedEdges, oppositeGraph, addedEdges)) //3.2.4
                                return true;
                    }
                }
                if (stage >= 4 && level == 0 && FECR && FindEdgesConstantlyRemoved(a_, graphArgument, oppositeGraphArgument, removedEdges, oppositeGraph)) //5
                    return true;
                if ((graphArgument[a_].Count == 1 && SearchForCycleAmongVerticesOfDegreeEqual1(graphArgument, a_)) //4.1.1
                    || (graphArgument[a_].Count > 1 && SearchForCycleAmongVerticesOfDegreeGreaterThan1(a_, graphArgument, oppositeGraphArgument))) //4.1.2
                    return true;
            }
            return HamiltonianCycleCantExist;
        }
        static bool UniqueNeighboursTest(int a, List<int>[] graphArgument, List<int>[] oppositeGraphArgument, List<Edge> removedEdges, bool oppositeGraph, List<int> addedEdges) //3.2.1
        {
            foreach (int e in addedEdges)
                AddEdge(new Edge(a, e), graphArgument, oppositeGraphArgument);
            verticesWithSubsets = GetVerticesWithSubsets(a, graphArgument);
            if (verticesWithSubsets.Count + 1 > graphArgument[a].Count) //4.2
            {
                foreach (int e in addedEdges)
                    RemoveEdge(new Edge(a, e), graphArgument, oppositeGraphArgument, new List<Edge>());
                return true;
            }
            else if (verticesWithSubsets.Count + 1 == graphArgument[a].Count)
            {
                for (int b = 0; b < graphArgument.Length; ++b)
                    if (!verticesWithSubsets.Contains(b) && a != b)
                        foreach (int c in graphArgument[a])
                            if (graphArgument[b].Contains(c))
                            {
                                if (!oppositeGraph)
                                    RemoveEdge(new Edge(b, c), graphArgument, oppositeGraphArgument, removedEdges);
                                else
                                    RemoveEdge(new Edge(c, b), oppositeGraphArgument, graphArgument, removedEdges);
                            }
            }
            foreach (int e in addedEdges)
                RemoveEdge(new Edge(a, e), graphArgument, oppositeGraphArgument, new List<Edge>());
            return false;
        }
        static List<int> GetVerticesWithSubsets(int a, List<int>[] graphArgument) //Vertices with subsets = vertices whose adjacency lists are subsets of a's adjacency list
        {
            List<int> list = new List<int>();
            for (int b = 0; b < graphArgument.Length; ++b)
                if (a != b)
                    if (IsSubset(graphArgument[a], graphArgument[b]))
                        list.Add(b);
            return list;
        }
        static void GetAddedEdges(int a, List<int>[] graphArgument, List<List<int>> list, List<int> addedEdges) //3.2.3
        {
            for (int b = 0; b < graphArgument.Length; ++b)
                if (a != b)
                    if (AtLeastOneCommonVertex(graphArgument[a], graphArgument[b]))
                    {
                        List<int> edges = new List<int>();
                        foreach (int edge in addedEdges)
                            edges.Add(edge);
                        foreach (int e in graphArgument[b])
                            if (!graphArgument[a].Contains(e) && a != e)
                                edges.Add(e);
                        if (edges.Count > 0 && !ListWasAdded(list, edges))
                            list.Add(edges);
                    }
        }
        static void SearchForCombinationOfAddedEdges(int a, int vertex, List<int>[] graphArgument, List<AddedEdges> listOfAddedEdges)
        {
            if (!combinationFound && timer.ElapsedMilliseconds < limit)
            {
                List<int> edges = new List<int>();
                List<int> vertices = new List<int>();
                foreach (int b in listOfAddedEdges[a].edges)
                    if (!addedEdges.Contains(b))
                    {
                        addedEdges.Add(b);
                        edges.Add(b);
                    }
                foreach (int b in listOfAddedEdges[a].verticesWithSubsets)
                    if (!newVerticesWithSubsets.Contains(b) && !originalVerticesWithSubsets.Contains(b))
                    {
                        newVerticesWithSubsets.Add(b);
                        vertices.Add(b);
                    }
                for (int b = 0; b < graphArgument.Length; ++b)
                    if (!newVerticesWithSubsets.Contains(b) && !originalVerticesWithSubsets.Contains(b) && IsSubset(graphArgument[vertex].Concat(addedEdges).Distinct().ToList(), graphArgument[b])) //Test if vertex is a vertex with subset
                    {
                        newVerticesWithSubsets.Add(b);
                        vertices.Add(b);
                    }
                if (originalVerticesWithSubsets.Count + newVerticesWithSubsets.Count >= graphArgument[vertex].Count + addedEdges.Count)
                    combinationFound = true;
                for (int b = a + 1; b < listOfAddedEdges.Count && !combinationFound; ++b)
                {
                    if (!IsSubset(addedEdges, listOfAddedEdges[b].edges) && !IsSubset(newVerticesWithSubsets, listOfAddedEdges[b].verticesWithSubsets))
                        SearchForCombinationOfAddedEdges(b, vertex, graphArgument, listOfAddedEdges);
                }
                if (!combinationFound)
                {
                    foreach (int b in edges)
                        addedEdges.Remove(b);
                    foreach (int b in vertices)
                        newVerticesWithSubsets.Remove(b);
                }
            }
        }
        static bool ListWasAdded(List<List<int>> lists, List<int> list)
        {
            foreach (List<int> list_ in lists)
                if (ListsAreEqual(list_, list))
                    return true;
            return false;
        }
        static bool ListsAreEqual(List<int> firstList, List<int> secondList)
        {
            if (firstList.Count != secondList.Count)
                return false;
            foreach (int a in firstList)
                if (!secondList.Contains(a))
                    return false;
            return true;
        }
        static bool IsSubset(List<int> firstList, List<int> secondList) //Returns true if secondList is a subset of firstList
        {
            if (secondList.Count > firstList.Count)
                return false;
            foreach (int a in secondList)
                if (!firstList.Contains(a))
                    return false;
            return true;
        }
        static bool AtLeastOneCommonVertex(List<int> firstList, List<int> secondList)
        {
            if (secondList.Count > firstList.Count)
                return false;
            foreach (int a in firstList)
                if (secondList.Contains(a))
                    return true;
            return false;
        }
        static bool FindEdgesConstantlyRemoved(int a, List<int>[] graphArgument, List<int>[] oppositeGraphArgument, List<Edge> removedEdges, bool oppositeGraph) //5
        {
            List<Edge>[] arrayOfRemovedEdges = new List<Edge>[2];
            if (graphArgument[a].Count == 1)
                return false;
            for (int b = 0; b < graphArgument[a].Count; ++b)
            {
                List<int>[] graph_ = SaveGraph(graphArgument);
                List<int>[] oppositeGraph_ = GetOppositeGraph(graph_);
                List<Edge> edges = new List<Edge>();
                int chosenVertex = graph_[a][b];
                graph_[a].Remove(chosenVertex);
                if (graph_[chosenVertex].Remove(a))
                {
                    edges.Add(new Edge(chosenVertex, a));
                    oppositeGraph_[a].Remove(chosenVertex);
                }
                foreach (int c in graph_[a])
                {
                    edges.Add(new Edge(a, c));
                    oppositeGraph_[c].Remove(a);
                }
                graph_[a].Clear();
                graph_[a].Add(chosenVertex);
                int numberOfRemovedEdges = edges.Count;
                bool HamiltonianCycleCantExist = AnalyzeGraph(graph_, oppositeGraph_, edges, false, false);
                if (HamiltonianCycleCantExist)
                {
                    if (!oppositeGraph)
                        removedEdges.Add(new Edge(a, chosenVertex));
                    else
                        removedEdges.Add(new Edge(chosenVertex, a));
                    graphArgument[a].Remove(chosenVertex);
                    oppositeGraphArgument[chosenVertex].Remove(a);
                    --b;
                }
                else
                {
                    edges.RemoveRange(0, numberOfRemovedEdges);
                    if (arrayOfRemovedEdges[0] == null)
                        arrayOfRemovedEdges[0] = edges;
                    else
                        arrayOfRemovedEdges[1] = edges;
                    if (arrayOfRemovedEdges[1] != null)
                        for (int d = 0; d < arrayOfRemovedEdges[0].Count; ++d)
                        {
                            bool found = false;
                            foreach (Edge e in arrayOfRemovedEdges[1])
                                if (arrayOfRemovedEdges[0][d].from == e.from && arrayOfRemovedEdges[0][d].to == e.to)
                                {
                                    found = true;
                                    break;
                                }
                            if (!found)
                            {
                                arrayOfRemovedEdges[0].RemoveAt(d);
                                --d;
                            }
                        }
                }
            }
            if (graphArgument[a].Count == 0)
                return true;
            foreach (Edge e in arrayOfRemovedEdges[0])
            {
                if (!oppositeGraph)
                    removedEdges.Add(e);
                else
                    removedEdges.Add(new Edge(e.to, e.from));
                graphArgument[e.from].Remove(e.to);
                oppositeGraphArgument[e.to].Remove(e.from);
            }
            return false;
        }
        static void FindImporatantVertices(int a, List<int>[] graphArgument, List<int> changedVertices) //9.2.2
        {
            for (int b = 0; b < graphArgument.Length; ++b)
                if (a != b)
                    if (IsSubset(graphArgument[b], graphArgument[a]) && !changedVertices.Contains(b))
                        changedVertices.Add(b);
        }
        static bool SearchForCycleAmongVerticesOfDegreeEqual1(List<int>[] graphArgument, int a) //4.1.1
        {
            List<int> cycle = new List<int>() { a };
            while (true)
                if (graphArgument[cycle.Last()].Count == 1 && cycle.Count < graphArgument.Length)
                    if (cycle.Contains(graphArgument[cycle.Last()][0]))
                        return true;
                    else
                        cycle.Add(graphArgument[cycle.Last()][0]);
                else
                    return false;
        }
        static bool SearchForCycleAmongVerticesOfDegreeGreaterThan1(int a, List<int>[] graphArgument, List<int>[] oppossiteGraphArgument) //4.1.2
        {
            if (!ListsAreEqual(graphArgument[a], oppossiteGraphArgument[a]) || graphArgument[a].Count >= graphArgument.Length / 2)
                return false;
            int b = 1;
            for (int c = 0; c < graphArgument.Length && graphArgument.Length - c > graphArgument[a].Count - b; ++c)
            {
                if (c == a)
                    continue;
                if (IsSubset(graphArgument[a], graphArgument[c]) && ListsAreEqual(graphArgument[c], oppossiteGraphArgument[c]))
                    ++b;
                if (b == graphArgument[a].Count)
                    return true;
            }
            return false;
        }
        static bool GraphIsDisconnected(List<int>[] graphArgument) //4.3
        {
            Stack<int> stack = new Stack<int>();
            Color[] colors = new Color[graphArgument.Length];
            colors[0] = Color.Gray;
            stack.Push(0);
            while (stack.Count > 0)
            {
                int a = stack.Pop();
                foreach (int b in graphArgument[a])
                    if (colors[b] == Color.White)
                    {
                        colors[b] = Color.Gray;
                        stack.Push(b);
                    }
                colors[a] = Color.Black;
            }
            foreach (Color c in colors)
                if (c != Color.Black)
                    return true;
            return false;
        }
        static List<int>[] GetReversedGraph(List<int>[] graphArgument) //6
        {
            List<int>[] graph = new List<int>[graphArgument.Length];
            for (int a = 0; a < graphArgument.Length; ++a)
                graph[a] = new List<int>();
            for (int a = 0; a < graphArgument.Length; ++a)
                foreach (int b in graphArgument[a])
                    graph[graphArgument.Length - 1 - a].Add(graphArgument.Length - 1 - b);
            return graph;
        }
        static void SortList(int a) //7.4
        {
            List<int> correctOrder = GetCorrectOrder(oppositeGraph);
            for (int b = 1; b < graph[a].Count; ++b)
                for (int c = 0; c < graph[a].Count - 1; ++c)
                    if (correctOrder.IndexOf(graph[a][c]) > correctOrder.IndexOf(graph[a][c + 1]))
                    {
                        int n = graph[a][c];
                        graph[a][c] = graph[a][c + 1];
                        graph[a][c + 1] = n;
                    }
        }
        static List<int> GetCorrectOrder(List<int>[] graphArgument) //7.2
        {
            Dictionary<int, int> vertices = new Dictionary<int, int>();
            List<int> order = new List<int>();
            for (int a = 0; a < graphArgument.Length; ++a)
                vertices.Add(a, graphArgument[a].Count);
            IEnumerable<int> v = from pair in vertices orderby pair.Value ascending select pair.Key;
            foreach (int a in v)
                order.Add(a);
            return order;
        }
        static void AddEdge(Edge e, List<int>[] graphArgument, List<int>[] oppositeGraphArgument)
        {
            graphArgument[e.from].Add(e.to);
            oppositeGraphArgument[e.to].Add(e.from);
        }
        static void RemoveEdge(Edge e, List<int>[] graphArgument, List<int>[] oppositeGraphArgument, List<Edge> removedEdges)
        {
            graphArgument[e.from].Remove(e.to);
            oppositeGraphArgument[e.to].Remove(e.from);
            removedEdges.Add(e);
        }
        static void RemoveMultipleEdgesAndLoops(List<int>[] graphArgument) //3.1
        {
            for (int a = 0; a < graphArgument.Length; ++a)
            {
                graphArgument[a] = graphArgument[a].Distinct().ToList();
                graphArgument[a].Remove(a);
            }
        }
        static List<int>[] GetOppositeGraph(List<int>[] graphArgument) //2.7
        {
            List<int>[] oppositeGraph = new List<int>[graphArgument.Length];
            for (int a = 0; a < graphArgument.Length; ++a)
                oppositeGraph[a] = new List<int>();
            for (int a = 0; a < graphArgument.Length; ++a)
                foreach (int b in graphArgument[a])
                    oppositeGraph[b].Add(a);
            return oppositeGraph;
        }
        static void RestoreGraphs(List<int>[] graphArgument)
        {
            graph = SaveGraph(graphArgument);
            oppositeGraph = GetOppositeGraph(graph);
        }
        static List<int>[] SaveGraph(List<int>[] graphArgument)
        {
            List<int>[] savedGraph = new List<int>[graphArgument.Length];
            for (int a = 0; a < graphArgument.Length; ++a)
            {
                savedGraph[a] = new List<int>();
                savedGraph[a].AddRange(graphArgument[a]);
            }
            return savedGraph;
        }
    }
    class Edge
    {
        public int from, to;
        public Edge(int f, int t)
        {
            from = f;
            to = t;
        }
    }
    class AddedEdges
    {
        public List<int> edges, verticesWithSubsets;
        public AddedEdges(List<int> edges_, List<int> vertices_)
        {
            edges = edges_;
            verticesWithSubsets = vertices_;
        }
    }
    enum Color { White, Gray, Black };
}